package my.jwds.p18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {


        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();

            int prev = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length-3; i++) {
                int num1 = nums[i];
                if (num1 == prev) continue;
                prev = num1;

                int num2Prev = Integer.MAX_VALUE;


                for (int j = i+1; j < nums.length-2; j++) {
                    int num2 = nums[j];
                    if (num2 == num2Prev)continue;
                    num2Prev = num2;


                    int num3Prev = Integer.MAX_VALUE;
                    int num4Index = nums.length -1;
                    for (int k = j+1; k < num4Index; k++) {
                        int num3 = nums[k];
                        if (num3 == num3Prev)continue;
                        num3Prev = num3;


                        int sum = -1;
                        while(num4Index!=k){
                            int num4 = nums[num4Index--];
                            sum = num1+num2+num3+num4;
                            if (sum <=target)
                                break;
                        }
                        if (sum < target){
                            num4Index ++;
                            continue;
                        }
                        if (sum == target){
                            List<Integer> list = new ArrayList<>();
                            list.add(num1);
                            list.add(num2);
                            list.add(num3);
                            list.add(target-num1-num2-num3);
                            res.add(list);
                            continue;
                        }
                    }

                }


            }
            return res;
        }

    }
}